package com.kk.datastructure.stack.poland;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * title: 后缀表达式计算
 * @author 阿K
 * 2020年11月30日 下午9:15:47 
 */
public class PolandNotAction {

	public static void main(String[] args) {
		
		//先定义给逆波兰表达式
		//(30+4)×5-6  => 30 4 + 5 × 6 - => 164
		String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
		List<String> list = getListString(suffixExpression);
		System.out.println("List=" + list);
		int res = calculate(list);
		System.out.println("计算的结果是=" + res);
		
	}
	
	// 将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
	public static List<String> getListString(String suffixExpression){
		//将 suffixExpression用空格进行分割分割
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String s:split) {
			list.add(s);
		}
		return list;
	}
	
	// 对逆波兰表达式进行运算
	public static int calculate(List<String> ls) {
		// 创建一个栈，用于存储依次弹出计算
		Stack<String> stack = new Stack<String>();
		
		// 遍历ls，计算入栈
		for(String item:ls) {
			// 使用正则取数，匹配多位数字（1 或者 12 等等...）
			if(item.matches("\\d+")) {
				// 入栈
				stack.push(item);
			}else {
				// pop出两个数，并运算， 再入栈
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res = 0;
				if("+".equals(item)) res=num1+num2;
				else if("-".equals(item)) res = num1-num2;
				else if("*".equals(item)) res = num1*num2;
				else if("/".equals(item)) res = num1/num2;
				else throw new RuntimeException("运算符有误");
				// 运算后入栈
				stack.push(""+res);
			}
		}
		// 最后留在stack中的数据是运算结果
		return Integer.parseInt(stack.pop());
	}
}
